package kyssion.leetcode.num201_250;

public class code211_最大正方形 {

    public static void main(String[] args) {
        System.out.println(new code211_最大正方形().maximalSquare2(
                new char[][]{
                        {'1', '1', '1', '0', '1'},
                        {'1', '1', '1', '1', '1'},
                        {'1', '1', '1', '0', '1'},
                        {'1', '0', '1', '1', '1'}
                }
        ));
//        System.out.println(new code211_最大正方形().maximalSquare2(
//                new char[][]{
//                        {'1', '0'},
//                        {'0', '1'},
//                        {'0', '1'},
//                        {'0', '1'},
//                        {'1', '1'},
//                        {'0', '0'},
//                        {'0', '1'}}
//        ));
    }

    /**
     * @param matrix
     * @return
     */
    public int maximalSquare2(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int lineLength = matrix[0].length;
        int[] dpX = new int[lineLength];
        int[] dpL = new int[lineLength];
        int[] dpR = new int[lineLength];
        int maxArr = 0;
        for (int a = 0; a < matrix.length; a++) {
            for (int b = 0; b < lineLength; b++) {
                dpL[b] = matrix[a][b] == '0' ? 0 : b == 0 ? 1 : dpL[b - 1] + 1;
                dpR[b] = matrix[a][b] == '0' ? 0 : dpR[b] + 1;
            }
            for (int b = lineLength - 1; b > 0; b--) {
                if (matrix[a][b] == '0' || dpL[b - 1] == 0 || dpR[b - 1] == 0) {
                    dpX[b] = 0;
                }
                if (dpX[b - 1] + 1 >= Math.min(dpL[b], dpR[b])) {
                    dpX[b] = Math.min(dpL[b], dpR[b]);
                } else {
                    dpX[b] = dpX[b - 1] + 1;
                }
                maxArr = Math.max(dpX[b], maxArr);
            }
            dpX[0] = matrix[a][0] == '0' ? 0 : 1;
            maxArr = Math.max(dpX[0], maxArr);
        }
        return maxArr * maxArr;
    }

    /**
     * 算法是o(n^3) 复杂度的,而且有点复杂....暂时过不了
     *
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }

        int[][] matrixInt = new int[matrix.length][matrix[0].length];
        int line = matrix[0].length;

        for (int a = 0; a < matrix.length; a++) {
            for (int b = 0; b < matrix[a].length; b++) {
                if (a == 0) {
                    matrixInt[a][b] = matrix[a][b] - '0';
                } else {
                    matrixInt[a][b] = matrix[a][b] == '0' ? 0 : matrixInt[a - 1][b] + 1;
                }
            }
        }

        int[][] indexInfo = new int[2][line];
        int index = 0;
        int maxArr = 0;
        for (int a = 0; a < matrix.length; a++) {
            index = 0;
            for (int b = 0; b < matrix[a].length; b++) {
                int nowHeight = 0;
                if (b == 0) {
                    indexInfo[0][b] = 0;
                    indexInfo[1][b] = matrixInt[a][b];
                    nowHeight = indexInfo[1][b] != 0 ? 1 : 0;
                    index++;
                } else {
                    int itemheight = matrixInt[a][b];
                    //使用前向数组,找到itemHeigth 对应的最远左向
                    for (int c = index - 1; c >= 0; c--) {
                        if (indexInfo[0][c] > b - itemheight + 1) {
                            nowHeight = itemheight;
                            break;
                        } else {
                            if (indexInfo[1][c] == 0) {
                                nowHeight = itemheight;
                                break;
                            }
                            if (indexInfo[1][c] < itemheight) {
                                itemheight = indexInfo[1][c];
                            }
                        }
                    }
                    while (index > 0) {
                        if (indexInfo[1][index] <= matrixInt[a][b]) {
                            break;
                        }
                        index--;
                    }
                    indexInfo[0][index] = b;
                    indexInfo[1][index] = matrixInt[a][b];
                    index++;
                }
                maxArr = Math.max(nowHeight * nowHeight, maxArr);
            }
        }
        return maxArr * maxArr;
    }

}
